{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.1 States\n",
    "\n",
    "* [Vector notation](./1-Basic_Quantum_Concepts/1-States.ipynb#vectornotation)\n",
    "* [Classical bits](./1-Basic_Quantum_Concepts/1-States.ipynb#classicalbits)\n",
    "* [Quantum bits – qubits](./1-Basic_Quantum_Concepts/1-States.ipynb#quantumbits)   \n",
    "* [Superposition](./1-Basic_Quantum_Concepts/1-States.ipynb#superposition)   \n",
    "* [2-Norm approach](./1-Basic_Quantum_Concepts/1-States.ipynb#normapproach)\n",
    "    * [Q# exercise: setup a Q# environment](./1-Basic_Quantum_Concepts/1-States.ipynb#qexercise)\n",
    "\n",
    "## Vector notation\n<a id='#vectornotation'></a>",
    "\n",
    "In physics, one describes the \"condition\" of a system as a \"state\". It may be understood as an indicator of\n",
    "a system's status – is a switch \"off\" or \"on\"; is the temperature in a room \"low\" or \"high\"; is a light \"red\"\n",
    "or \"green\", is a flipped coin \"tail\" or \"head\", etc. A state of a system does not necessarily need to be binary.\n",
    "But these examples are chosen conveniently to be binary because historically computers are built on\n",
    "binary systems. Mathematically, these states can be represented with two numbers: 0 and 1.\n",
    "\n",
    "![Figure 1.1.1 states](media/states.png)\n",
    "\n",
    "We denote a state with symbol $| \\rangle$ (pronounced as \"ket\"; see _Physics insert - Dirac notation_ in section\n",
    "1.2.4). With two numbers, one can write the two states using two [basis vectors](https://en.wikipedia.org/wiki/Basis_(linear_algebra)) as\n",
    "\n",
    "$|0\\rangle =\\binom{1}{0} , |1\\rangle =\\binom{0}{1}$.\n",
    "\n",
    "This is the definition of |0⟩ and |1⟩ states. Note that the 0 and 1 in | ⟩ have a different meaning from the\n",
    "ones in the vectors. We could give non-numerical labels to the states, such as $|a\\rangle $, $|\\Psi\\rangle$, $|function\\rangle$, etc.\n",
    "\n",
    "## Classical bits\n<a id='#classicalbits'></a>",
    "\n",
    "|0⟩ and |1⟩ states above are two single classical bits. We can represent multi-bit states with vectors as well. Multi-bit states are [Kronecker products](https://en.wikipedia.org/wiki/Kronecker_product) of single bits. For example, state |00⟩ has two bits, both being 0. We obtain |00⟩ by doing a Kronecker product of two |0⟩ states, denoted as |0⟩⊗|0⟩ (see how to do Kronecker product in _Math insert - Kronecker product_ ). This yields\n",
    "\n",
    "$|00\\rangle = \\binom{1}{0} \\otimes \\binom{1}{0}=\\begin{pmatrix} 1\\\\0\\\\0\\\\0 \\end{pmatrix}.$\n",
    "\n",
    "Similarly,\n",
    "\n",
    "$|01\\rangle = \\binom{1}{0} \\otimes \\binom{0}{1}=\\begin{pmatrix} 0\\\\1\\\\0\\\\0 \\end{pmatrix}$,\n",
    "\n",
    "$|10\\rangle = \\binom{0}{1} \\otimes \\binom{1}{0}=\\begin{pmatrix} 0\\\\0\\\\1\\\\0 \\end{pmatrix}$,\n",
    "\n",
    "$|11\\rangle = \\binom{0}{1} \\otimes \\binom{0}{1}=\\begin{pmatrix} 0\\\\0\\\\0\\\\1 \\end{pmatrix}$.\n",
    "\n",
    "As can be seen, a complete set of two bits is represented with four basis vectors, each with four elements. When a system has $N$ bits, we will need $2N$ basis vectors each with $2N$ elements to describe it.\n",
    "\n",
    "![Figure 1.1.2 states](media/multiple_qubits.png)\n",
    "\n",
    "\n",
    ">_Math insert - Kronecker product_------------------------------------------------------------------------\n",
    ">\n",
    ">How does Kronecker product $\\otimes$ work?\n",
    ">\n",
    ">$\\binom{x_{0}}{x_{1}} \\otimes \\binom{y_{0}}{y_{1}} = \\binom{x_{0}\\binom{y_{0}}{y_{1}}}{x_{1}\\binom{y_{0}}{y_{1}}} = \\begin{pmatrix} x_{0}y_{0}\\\\x_{0}y_{1}\\\\x_{1}y_{0}\\\\x_{1}y_{1} \\end{pmatrix} $\n",
    ">and\n",
    ">$\\binom{x_{0}}{x_{1}} \\otimes \\binom{y_{0}}{y_{1}} \\otimes \\binom{z_{0}}{z_{1}} = \\begin{pmatrix} x_{0}y_{0}z_{0}\\\\x_{0}y_{0}z_{1}\\\\x_{0}y_{1}z_{0}\\\\x_{0}y_{1}z_{1}\\\\x_{1}y_{0}z_{0}\\\\x_{1}y_{0}z_{1}\\\\x_{1}y_{1}z_{0}\\\\x_{1}y_{1}z_{1} \\end{pmatrix} $\n",
    ">and so on. \n",
    ">\n",
    ">For example, the number 4 can be represented with a three-bit string 100. We can write\n",
    "> \n",
    ">$|4\\rangle = |100\\rangle = \\binom{0}{1} \\otimes \\binom{1}{0} \\otimes \\binom{1}{0} = \\begin{pmatrix} 0\\\\0\\\\0\\\\0\\\\1\\\\0\\\\0\\\\0 \\end{pmatrix}$.\n",
    ">\n",
    "\n",
    "## Quantum bits – qubits\n <a id='#quantumbits'></a>",
    "\n",
    "It turns out that |0⟩ and |1⟩ are just two special cases in quantum computing. Generally, when there is\n",
    "one qubit, the system can be in a state $|\\Psi\\rangle$ that has some portions of both |0⟩ and |1⟩ states in it.\n",
    "Mathematically, $|\\Psi\\rangle$ is a linear combination or **superposition** of |0⟩ and |1⟩, i.e.\n",
    "\n",
    "$|\\Psi\\rangle = \\binom{a}{b} = a |0\\rangle + b |1\\rangle$, \n",
    "\n",
    "where $a$ and $b$ are two constants and can be complex numbers (see _Math insert – complex numbers_). $a$ and $b$ are essentially describing how much of |0⟩ and |1⟩ are in the system. They are the \"weights\" and in\n",
    "fact amplitudes (see \"wavefunction\") of the |0⟩ and |1⟩ states. Their magnitude squared, $|a|^{2}$ and $|b|^{2}$,\n",
    "give the probabilities of finding the system in |0⟩ and |1⟩, respectively. Therefore $|a|^{2}$ and $|b|^{2}$ \n",
    "can be anything as long as the total probably sums up to 1, that is $\\left| a \\right|^{2} + \\left| b \\right|^{2} = 1$. \n",
    "This is referred to as the normalization condition.\n",
    "\n",
    "![Figure 1.1.3 states](media/spinning_coin.png)\n",
    "\n",
    "When the system has two qubits, there are four basis states the system can be in, where\n",
    "\n",
    "$|\\Psi\\rangle = \\binom{a}{b} \\otimes \\binom{c}{d} = \\begin{pmatrix} ac\\\\ad\\\\bc\\\\bd \\end{pmatrix} = ac|00\\rangle + ad|01\\rangle + bc|10\\rangle + bd|11\\rangle$.\n",
    "\n",
    "The normalization condition writes as $|ac|^{2} + |ad|^{2} + |bc|^{2} + |bd|^{2} = 1$. \n",
    "With $N$ qubits, there are $2^{N}$ possible states the system can be in.\n",
    "\n",
    "\n",
    ">_Math insert – complex numbers_ ----------------------------------------------------------------------------------\n",
    ">\n",
    ">A complex number has a linear form, $z=a+bi$, where $a$ and $b$ are real numbers and $i\\equiv \\sqrt (-1)$ is an imaginary number, so that a complex number has a real part $Re(z)$  and an imaginary part $Im(z)$. \n",
    ">It is a mathematical convenience to ensure a square-root of a negative number to have a solution, since there is no real-number solution. This is useful in quantum mechanics as wave equations (below) will be easier to solve.  \n",
    ">A complex number can also be represented in a polar form, $z=re^{i\\varphi}$, where $r=\\sqrt(a^2+b^2)$ is the amplitude or the **absolute value** of $z$, and $\\varphi$ is the phase or **argument** of $z$. It follows the relations $\\varphi=atan2(Im(z), Re(z))=\\tan^{-1}\\left ( \\frac{b}{a} \\right )$ and $e^{i\\varphi} = \\cos ⁡\\varphi + i\\sin⁡ \\varphi$.\n",
    ">\tA one-qubit state $|\\Psi\\rangle = z_{0}|0\\rangle + z_{1}|1\\rangle$ can be written as\n",
    ">\n",
    ">$(a_{0}+b_{0})|0\\rangle + (a_{1}+b_{1})|1\\rangle$\n",
    ">\n",
    ">$=r_{0}e^{i\\varphi_{0}}|0\\rangle + r_{1}e^{i\\varphi_{1}}|1\\rangle$.\n",
    ">\n",
    ">Therefore, the probability of finding state $|0\\rangle$ is $|r_{0}e^{i\\varphi_{0}}|^2=r_{0}^2$. Similarly, for state $|0\\rangle$ it is $r_{1}^{2}$. The probability is determined by the magnitude of amplitude and is independent from phase.\n",
    ">\n",
    "\n",
    "## Superposition\n <a id='#superposition'></a>",
    "\n",
    "In math, superposition is just several functions linearly adding up. Here, we are dealing with states – one type of mathematical functions. Superposition of states is the fundamental factor that makes quantum computing powerful. Because while a classical bit can only be in either |0⟩ or |1⟩, a qubit can be in a state where |0⟩ and |1⟩ coexist – a complex linear combination between |0⟩ and |1⟩. Thus, if we make a computing system that can leverage this quantum phenomenon, we can have a single qubit that contains information where two classical bits would be needed. With $N$ qubits, the system can compute $2N$ classical bits of information.\n",
    "\n",
    ">_Physics insert – wavefunction_ --------------------------------------------------------------------------\n",
    ">\n",
    ">We introduced the concept of states without requiring any physics background. However, it may be interesting for some readers to know how physics describes a quantum system.  Typically, physicists learn the subject in a chronological order – how the field of Physics has developed through time. Because physicists were used to classical phenomena, experimental results of quantum mechanical phenomena appeared to be >surprising when they were first observed (look up the “UV Catastrophe”, “photoelectric effect”, “Compton Effect” and “interference of light at low intensity”). Physicists in the early 1900s naturally attempted to explain the results using classical methods. \n",
    ">These unexpected observations have led to the metaphors one often hears about in popular science today. These metaphors tend to make quantum physics sound mysterious and often hinder more than help one’s understanding. Now that we are in the 21st century, quantum concepts can be taught in a much more straight-forward way, based on all the accumulated knowledge. This is the approach this tutorial takes to teach >quantum computing – giving readers direct and enough information to get started with quantum computing while introducing historical facts from physics where appropriate for context. This way, readers will not be confused through unnecessary information overload but can still appreciate the thought physicists have put into developing the field. \n",
    ">One of the historical approaches to describe quantum phenomena is using wavefunctions. Physicists in the early 1900s found that quantum particles behave like waves. This means a quantum system can be described using a wave equation - the Schrödinger equation. Here is the Schrödinger equation for a non-relativistic particle in an external potential: \n",
    ">\n",
    ">$-\\frac{\\hbar^{2}}{2m} \\nabla^{2} \\psi(r,t)+V(r,t)\\psi(r,t)=i\\hbar \\frac{\\partial \\psi(r,t)}{\\partial t}  $,                                           \n",
    ">\n",
    ">where $\\psi $, called the “wavefunction,” describes the state of the particle (technically, $|\\psi(r,t)|^{2}$ is the probability of finding the particle at position $r$ at time $t$); $\\hbar$ is Planck constant (~1.05 x 10-34 Js/rad); $m$ is the mass of the quantum particle; and $V$ is an external potential (such as an electric or gravitational field). ). In a system that doesn’t vary with time, the right-hand side of >the equation equals $E\\psi(r,t)$, with $E$ being the energy of the system.  The above equation reflects conservation of energy, as the first and second parts on the left-hand side describe the kinetic energy and potential energy in the system, respectively. Something that’s very important to note is that in the above equation, $\\phi(r,t)$ is a field that fills all of space and which evolves with time, which has to do >with the probability of finding the particle anywhere at a given time. This is very different from classical mechanics, where we deal with the exact locations of particles.\n",
    ">Physicists have established a rigorous representation of quantum systems using wavefunctions. However, an in-depth formalism with this approach is beyond the scope of this tutorial and is not essential for a quantum computing introduction. Thus, we avoid going into details of the “wave” approach but state its relevant outcomes next.     \n",
    ">\n",
    ">\n",
    ">_Physics insert – Dirac notation_ -------------------------------------------------------------------------\n",
    ">\n",
    ">Manipulating wavefunctions usually involves a lot of integrals. It tends to look messy. Paul Dirac came up with a compact and abstract notation. We’ve been using the symbol $| \\rangle$ to indicate states: $| \\psi \\rangle$ denotes “the state with wavefunction” $\\psi(r,t)$ . It has a counterpart representing its conjugate $\\psi^{*} (r,t)= \\langle \\space |$. Together they form their overlap integral or inner product >defined as\n",
    ">\n",
    ">$\\int_{-\\infty}^{+\\infty} \\phi^{*}(x)\\psi(x) dx \\equiv \\langle \\phi|\\psi\\rangle $.\n",
    ">\n",
    ">Evidently, the Dirac notation is much more concise. The inner product $\\langle | \\rangle$ is a shorthand for an integral and is pronounced as “bracket”. The symbols “bra”, $\\langle |$, and “ket”, $| \\rangle$, are shorthand for wavefunctions. If $\\psi(x)$ is normalized, $\\langle \\psi | \\psi\\rangle = 1$.\n",
    ">\n",
    ">_Physics insert – superposition_ --------------------------------------------------------------------------\n",
    ">\n",
    ">The Schrödinger equation has a very interesting property called “linearity.” If we find two solutions $\\psi_{1}$ and $\\psi_{2}$, then combinations of them are also a valid solution. For example, $\\frac{1}{2} (\\psi_{1} + \\psi_{2} )$ is a solution. For any system, physicists find a set of “basis states”, which are sufficient to fully describe the system. For example, there might be one basis state for each position the particle >can be in. But now, since the Schrödinger equation is linear, the combination of multiple basis states is also a valid state. For example, the combination of the states representing “particle is at position 0” and “particle is at position 1” is valid and represents a state where the particle’s position is either 0 or 1. This is called the “superposition principle”.\n",
    ">The superposition behavior is written as\n",
    ">\n",
    ">$\\psi(x) = \\sum_{i} c_{i} \\phi_{i}(x)$,\n",
    ">\n",
    ">where we’re working in 1D (hence, $x$ instead of $r$) for simplicity. Here, $\\phi_{i}$ is the $i$th basis state in the system with coefficient $c_{i}$ being the “amplitude” of $\\phi_{i}$. The amplitude squared, $|c_{i}|^{2}$, gives the probability of the system being in the $i$th state, $\\phi_{i}$. Any wavefunction can be expanded in terms of the basis states, $\\phi_{i}(x)$.\n",
    ">\tIn terms of a qubit, the above equation is reflected by superposition of states, such as in $|\\psi\\rangle = c_{0} |0\\rangle + c_{1} |1\\rangle$. We can see that a qubit system has only two basis states.\n",
    ">To obtain the value of the coefficient of each possible basis state, one needs to find how much overlap there is between each basis state  $\\phi_{j}$  and the overall state $\\psi$. \n",
    ">\n",
    ">$\\int_{-\\infty}^{+\\infty} \\phi_{j}^{*}(x)\\psi(x) dx = \\sum_{i} c_{i} \\int_{-\\infty}^{+\\infty} \\phi_{j}^{*}(x)\\phi_{i} dx = c_{j}$.\n",
    ">\n",
    ">In Dirac notation, $|\\psi\\rangle = \\sum_{i}c_{i}|\\phi_{i}\\rangle$ , where $c_{j}= \\langle\\phi_{j}|\\psi\\rangle$. \n",
    ">\n",
    "\n",
    "## 2-Norm approach – an alternative way to teach and learn quantum mechanics\n <a id='#normapproach'></a>",
    "\n",
    "Now that we are in the 21st century, quantum phenomena are no longer so strange to physicists, given all the knowledge we have accumulated from the past experiments. Perhaps there is a more straightforward way to learn quantum mechanics, without needing to immediately think about wavefunctions. Scott Aaronson, a theoretical computer scientist at University of Texas, uses a different approach to introduce quantum mechanics: https://www.scottaaronson.com/democritus/lec9.html\n",
    "\n",
    "Essentially, we can start by generalizing probability theory. In our experience, probabilities are\n",
    "always positive and sum to 1. This is called the \"1-norm\" condition:\n",
    "\n",
    "$\\sum _{i} p_{i} = 1$ .\n",
    "\n",
    "In quantum mechanics, we don't work directly with probabilities. Instead, we work with\n",
    "\"amplitudes.\" The square of an amplitude is a probability, so we require that _squares_ of the amplitudes sum to 1. This is called the \"2-norm\" condition (where \"2\" refers to the fact that we're squaring the amplitudes):\n",
    "\n",
    "$\\sum _{i} | a_{i} |^{2} = 1$ .\n",
    "\n",
    "One thing to note here is that when we talk about \"squaring\" a number, we actually mean taking\n",
    "the \"modulus squared\" (or the \"square of the magnitude\"), which is done by multiplying it by its complex conjugate: $| a |^{2} = a^{*}a$. For a real number, taking the modulus squared and taking the square are the same thing, but for a complex number, they're different.\n",
    "\n",
    "Because of the 2-norm condition, an amplitude can be a positive, negative or even complex\n",
    "number. In the examples earlier, we wrote the amplitudes as $c_{i}$. As seen in the normalization condition, it is the square of _magnitudes_ of the amplitudes that sum to 1. Amplitudes are related to probabilities. If\n",
    "we want to go from an amplitude to a probability, we take the square of the magnitude of the amplitude. That's why the squares of the amplitudes must sum to 1.\n",
    "\n",
    "The complex number $c_{i}$ can be written as $r_{0}e^{i\\phi _{i}}$, with $r_{0}$ being the magnitude and $\\phi _{i}$ the phase (see earlier _Math insert – complex numbers_ ). Both $r_{0}$ and $\\phi _{i}$ are real numbers. As we've seen in _Math insert – complex numbers_ , probability only depends on the magnitude of the amplitude. For two\n",
    "amplitudes, the normalization condition is\n",
    "\n",
    "$\\left |c_{0}  \\right |^{2} + \\left |c_{1}  \\right |^{2} = \\left |r_{0}e^{i\\phi _{0}}  \\right |^{2} + \\left |r_{0}e^{i\\phi _{1}}  \\right |^{2} = r_{0}^{2}+r_{1}^{2} = 1$.\n",
    "\n",
    "This alternative quantum mechanics introduction bypasses wavefunction derivations. It puts up\n",
    "front that the universe behaves according to the 2-norm condition with a set of axioms. This allows us to see some fundamental quantum mechanical behaviors without dealing with more complicated systems, such as particles in an external potential. This is a useful fact when we talk about **measurements** in the next session.\n",
    "\n",
    "```\n",
    "To read more rigorous mathematical derivations of the axioms in modern quantum theory:\n",
    "```\n",
    "- https://arxiv.org/abs/quant-ph/0101012\n",
    "- https://arxiv.org/abs/1011.6451\n",
    "- https://arxiv.org/abs/quant-ph/0104088\n",
    "\n",
    "## Q# exercise: setup a Q# environment\n <a id='#qexercise'></a>",
    "\n",
    "\n",
    "Q# is a domain-specific programming language, developed by Microsoft, used for expressing quantum\n",
    "algorithms. We will be using it to gain hands-on experience programming quantum computers. There are\n",
    "several ways to exercise programming in Q#. The Microsoft Quantum Development Kit provides several\n",
    "open-source options. In this tutorial book, we will be choosing exercises developed on VS Code, Jupyter Notebooks and other tools. At the end of each session, we will familiarize ourselves by using a couple of these tools and hands-on coding. (The goal of the below exercise is to set up the environment and to take note of the katas, rather than to run a Q# program at the moment.)\n",
    "\n",
    "1. Install and validate [Quantum Development Kit](https://docs.microsoft.com/en-us/quantum/install-guide/?view=qsharp-preview) (choose between Visual Studio or Visual Studio\n",
    "    Code) according to the instructions \n",
    "2. Download or clone [QuantumComputingViaQSharpSolution that is a folder in this repository](https://github.com/microsoft/Reference-Guide-For-Quantum-Computing-A-Microsoft-Garage-Project/tree/main/QuantumComputingViaQSharpSolution) developed by Pavan Kumar.\n",
    "3. Look at the first script in 01_HelloQuantumWorld Operation.qs in Visual Studio Code. This is empty to show the structure of a Q# script. The body inside Operation():() is where the quantum algorithm will be written. We will learn how to write quantum operations in the next few chapters.   \n",
    "4. Take a look at the [Quantum Katas](https://github.com/microsoft/QuantumKatas) developed by Microsoft Quantum on Jupyter Notebook. We will choose from these katas after learning the concepts at each session. You can run the katas online as a Jupyter Notebook. If you wish to run them locally, follow the instructions on the section labeled 'Running the Katas Locally' to clone the repository onto your computer.\n",
    "5. All the quantum programming exercises we use here are open-source. You should feel free to contribute to them. \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.2-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38264bit9c6c9a68585e47979e5211bcda393816",
   "display_name": "Python 3.8.2 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
